A method and system for using tertiary operations in repairing Grounded Aircraft Routes, and more particularly a method and system for swapping flight sequences among a Grounded Aircraft Route, and two Available Aircraft Routes to cure the irregularities in the Grounded Aircraft Route in real time while maintaining time and space feasibility in both the Available Aircraft Routes and the Grounded Aircraft Route.
U.S. patent application Ser. No. 09/364,157 filed on Jul. 30, 1999, and assigned to the assignee of the present invention.
U.S. patent application Ser. No. 09/364,157, which is assigned to the assignee of the present application, discloses a real time aircraft optimization engine that uses Unary, Binary, and Three-Way Operations for repairing a Grounded Aircraft Route, a route of an aircraft which has been grounded for a specific period of time. The Unary Operations cancel and uncancel or do nothing to the Grounded Aircraft Routes. The Binary Operations repair a Grounded Aircraft Route through actions performed with one Available Aircraft Route, a route of an aircraft which is available for use in a solution of a flight schedule irregularity. Tertiary Operations are used to repair a Grounded Aircraft Route through actions with two Available Aircraft Routes. The system in which the aircraft optimization engine of the above patent application operates is illustrated in FIG. 1.
Referring to FIG. 1, a functional block diagram of the environment in which the invention operates is shown, where a user interface referred to as an Optimization Server 1 is in electrical communication with a user by way of a bidirectional communication path 2, and receives a request for optimal solutions to a specific flight schedule disruption. In response to the request, the Optimization Server 1 initializes an Aircraft Optimization Engine 3 by way of a bi-directional communication path 4, and provides the Aircraft Optimization Engine 3 an Aircraft Problem Specification. The Aircraft Optimization Engine 3 processes the Aircraft Problem Specification and generates a set of optimal solutions including aircraft reassignments and flight modifications to overcome the disruption. The solutions are transmitted over communication path 4, and through the Optimization Server 1 and bi-directional path 2 to the user.
The Aircraft Optimization Engine 3 further initializes a Crew Optimization Engine 5 by way of a bi-directional communication path 6 to determine whether the optimal flight solutions are efficiently supported by flight and service crews.
During operation, the Aircraft Optimization Engine 3 and the Crew Optimization Engine 5 communicate by way of bi-directional communication paths 10 and 11, respectively, with a memory system such as a disk storage unit 9 having stored therein memory objects containing all of the data used by the engines to solve problems. For example, the memory objects include instances of Station, Market, Aircraft, Fleet, Subfleet, Maintenance, and Flight classes, and are created and updated by the Data Collection Unit 12 and the Data Update Unit 13, respectively.
The Data Collection Unit 12 receives complete information for stations, markets, aircraft, fleets, subfleets, maintenance, and flights from the user by way of bi-directional communication path 14. Thereafter, the Data Collection Unit 12 creates memory objects which are supplied by way of a bi-directional communication path 15 for storage in the disk storage unit 9, and at memory locations specified by a Memory Mapping Unit 16 along a bi-directional communication path 17. Further, the Data Update Unit 13 receives revisions to the memory objects from the user over a bi-directional communication path 18, and supplies corrections through a bi-directional communication path 19 to the objects identified by the Memory Mapping Unit 16.
The Memory Mapping Unit 16 receives control signals from the user over a bi-directional communication path 20, and in response thereto identifies the addresses of the memory objects in the disk storage unit 9 which are being operated upon. By means of the Memory Mapping Unit 16 and the Data Update Unit 13, the user is able to keep the data stored in the Disk Storage Unit 9 current with the data being supplied to the user by way of communication path 2.
At any given time, the memory objects of the Disk Storage Unit 9 reflect the existing flight environment, including identifications of protected flights which are not to be canceled or delayed; flight sequences or routes for each aircraft; the stations or airports to be used by the aircraft; the fleets and subfleets assigned to each station; station closure times; fleet arrival and departure curfews; inviolable and violable maintenance schedules; aircraft seat capacities; fleet operational ground times; operations costs; flight disruption costs; subfleet disruption costs; and revenue and passenger information for each scheduled flight.
The Aircraft Problem Specification received by the Aircraft Optimization Engine 3 upon being initialized by a request from the user, further includes the identification of grounded aircraft; the stations where aircraft groundings have occurred; the start and end times of each of such groundings; the identification of available aircraft; the identification of protected flights; recovery period start and end times; maximum allowable flight delays; and flight cancellation and ferry creation restraints.
Based upon the above information a solution comprised of flight delays and cancellations, Ferry Flight creations, as well as aircraft reassignments is produced.
In the prior art invention disclosed in the above patent application, a solution is sought by first executing Unary Operations, then Binary Operations, and lastly Three-Way Operations until all Available Aircraft Routes have been processed to achieve solutions for all Grounded Aircraft Routes. See FIG. 3 of the above patent application. More particularly, Available Aircraft Routes are chosen two at a time, and a local neighborhood search is performed (i.e., the above set of operations are performed on the Grounded Aircraft Route to identify time and space feasible solutions), and thereafter two additional Available Aircraft Routes are chosen and the process repeated.
One Binary Operation that is disclosed is a Swap Operation in which flight sequences of one route are replaced with flight sequences of another route. A Three-Way Swap also is disclosed which is comprised of removing a first sequence of flights from a Grounded Aircraft Route, removing a second sequence of flights from a first Available Aircraft Route, removing a third sequence of flights from a second Available Aircraft Route, replacing the first sequence with the second sequence of flights, replacing the second sequence with the third sequence of flights, and replacing the third sequence with the first sequence of flights.
The above Three-Way Swap Operation requires three entities to be considered through a brute force method which is time consuming because three flights are considered at a same time, which is not tolerable in an environment demanding real time solutions such as occurs in aircraft flight schedules. In order to alleviate this problem, a solution is sought which would reduce problem complexity to a consideration of only two aircraft at a time by taking advantage of conditions found while performing Binary Operations that could be used in Tertiary Operations including Three-Way Swap Operations in accordance with the present invention. That is certain states found while performing Binary Operations are later used in Tertiary Operations in real time.
The definitions set forth in the Description of Preferred Embodiments and U.S. patent application Ser. No. 09/364,157 apply to this summary.
An improved method for conducting local neighborhood searches among three or more aircraft routes to cure any irregularity in a Grounded Aircraft Route, where states of previously executed Binary Operations performed on the Grounded Aircraft Route and Available Aircraft Routes are stored, time and space feasibility tables are created from the stored values, and Tertiary Operations (Three-Way Swap Operations and other operations conducted on three aircraft routes in accordance with the invention) related to said feasibility tables then are conducted on the Grounded Aircraft Route and Available Aircraft Routes to reconfigure each of the aircraft routes to effect a repair to the Grounded Aircraft Route in real time.
In one aspect of the invention, each flight sequence or subroute which is moved or swapped among aircraft routes must be time and space feasible. Further, for a Binary Operation to be feasible, both aFeas and gFeas must have a Boolean value of true. With Three-Way Swap Operations, only one of aFeas and gFeas need have a Boolean value of true. Other Tertiary Operations may have different combinations of aFeas and gFeas Boolean values.
In a second aspect of the invention, time and space feasible table pairs are generated from gFeas and aFeas values determined from Binary Operations conducted on a Grounded Aircraft Route and plural Available Aircraft Routes, and the tables are searched for matching Grounded Route Indices (gH,gT) to indicate that a Tertiary Operation is feasible. No additional evaluations except feasibility between Available Aircraft Routes need take place. Each entry in the tables captures the positions of the subroutes for both the Grounded Aircraft and an Available Aircraft that were used to perform a prior Binary Operation.
In another aspect of the invention, a Grounded Feasible Table and an Available Feasible Table are generated from known values of aFeas and gFeas, and the tables are searched for matching Grounded Route Indices (gH,gT) to indicate that a Three-Way Swap Operation is feasible. No additional evaluations except feasibility between Available Aircraft Routes need take place. Each entry in the tables captures the positions of the subroutes for both the Grounded Aircraft and an Available Aircraft that were used to perform a prior Binary Operation.
In a further aspect of the invention, Tertiary Operations include a Three-Way Swap Operation, and variants thereof which may consist of a Three-Way Swap Operation and another operation. Pivot Points occurring in either a Grounded Subroute or an Available Subroute that are produced by such a variant may be represented in one or both of the feasible tables needed for Tertiary Operations.
In still another aspect of the invention, each feasible table pair generated from values of aFeas and gFeas determined from Binary Operations conducted on a Grounded Aircraft Route and plural Available Aircraft Routes is specific to a particular Tertiary Operation. If either table contains no data, that particular Tertiary Operation is not performed. If both tables are populated, then that particular Tertiary Operation is performed to create new ones of the Grounded Aircraft Route, and Available Aircraft Routes upon which the operation was conducted.
In a still further aspect of the invention, certain of the Binary Operations conducted on the Grounded Aircraft Route, and the Available Aircraft Routes are detected to determine which Tertiary Operation tables will be created, and hence which Tertiary Operations will be performed.
In yet another aspect of the invention, an N-Way Swap Operation is provided for conducting a local neighborhood search of a Grounded Aircraft Route and Nxe2x88x921 Available Aircraft Routes to swap time and space feasible sequences of flights among all N routes to repair the Grounded Aircraft Route, where N is any whole number greater than or equal to 3.